
/**
 * 
 * 打印任务排序
 * 
 * 题目描述

某个打印机根据打印队列执行打印任务。

打印任务分为九个优先级，分别用数字 1-9 表示，数字越大优先级越高。

打印机每次从队列头部取出第一个任务 A，然后检查队列余下任务中有没有比A优先级更高的任务，如果有比 A 优先级高的任务，则将任务 A 放到队列尾部，否则就执行任务 A 的打印。

请编写一个程序，根据输入的打印队列，输出实际的打印顺序。

输入描述
输入一行，为每个任务的优先级，优先级之间用逗号隔开，优先级取值范围是1~9。

输出描述
输出一行，为每个任务的打印顺序，打印顺序从 0 开始，用逗号隔开。

用例
输入	9,3,5
输出	0,2,1
说明	
队列头部任务的优先级为9，最先打印，故序号为0；
接着队列头部任务优先级为3，队列中还有优先级为5的任务，优先级3任务被移到队列尾部；
接着打印优先级为5的任务，故其序号为1；
最后优先级为3的任务的序号为2。
输入	1,2,2
输出	2,0,1
说明	队列头部任务的优先级为1，被移到队列尾部；接着顺序打印两个优先级为2的任务，故其序号分别为0和1；最后打印剩下的优先级为1的任务，其序号为2

 * 
 */

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

/**
  * 
  题目解析
关于用例2的输出解释：

初始时，每个任务的索引位置和优先级已经给定，因此我们可以将输入转化为：

[1, 0]  // 优先级为1，初始排队序号为0
[2, 1]  // 优先级为2，初始排队序号为1
[2, 2]  // 优先级为2，初始排队序号为2
接下来开始打印头部任务[1, 0]，发现该任务的优先级不是最高的，因此需要将他取出压如队尾，即顺序变为：

[2, 1]  // 优先级为2，初始排队序号为1
[2, 2]  // 优先级为2，初始排队序号为2
[1, 0]  // 优先级为1，初始排队序号为0
接下来开始打印头部任务[2, 1]，发现该任务的优先级是最高的，因此将他取出后打印，

即排队序号为1的任务，打印序号是0，剩余任务顺序如下：

[2, 2]  // 优先级为2，初始排队序号为2
[1, 0]  // 优先级为1，初始排队序号为0
继续取出头部任务[2, 2]，发现发现该任务的优先级是最高的，因此将他取出后打印，

即排队序号为2的任务，打印序号是1，剩余任务顺序如下：

[1, 0]  // 优先级为1，初始排队序号为0
最后一个任务直接打印，即排队序号为0的任务，打印序号是2，

最后需要输出打印序号，但是需要按照排队序号的顺序输出。

排队序号为0的任务，打印序号是2，

排队序号为1的任务，打印序号是0

排队序号为2的任务，打印序号是1

通过上面逻辑的概述，我们可以使用链表结构来维护任务顺序，如下图所示：

[1, 0] → [2, 1] → [2, 2]
如果当前头部任务的优先级不是最高的，则取出后压入尾部

[2, 1] → [2, 2] → [1, 0]
如果当前头部任务的优先级是最高的，则取出

同时，为了记录打印序号，我们应该提前定义一个打印序号数组ans

比如上面头部[2, 1]取出后，说明排队序号1的任务，打印序号为0，即ans[1] = 0

还有一个问题，那就是如何判断当前头部任务的优先级是否是剩余任务中优先级最高的呢？

我的策略是，将输入的优先级数组 priorities，进行降序，那么初始时，最高优先级的任务在priorities数组的索引为 0

而最高优先级的任务，也是最先被打印的任务，我们可以定义一个变量 printIndex 表示当前最高优先级任务的索引位置（或者理解为当前打印序号）

取出链表头部任务 task
task.priority表示任务的优先级,
task.index表示任务的初始排队顺序序号
如果链表头部任务 task.priority == priorities[printIndex]，那么说明头部任务就是最高优先级的，即初始排队顺序为 task.index 的任务在 printIndex 的时候被打印。然后printIndex++，表示继续下一个打印任务
如果链表头部任务 task.priority != priorities[printIndex]，那么就将头部任务task重新加入队尾，此时 printIndex 保持不变。
循环上面操作，直到链表为空时结束。

这样的话，我们就找到了每个任务

初始排队顺序序号（task.index） -> 实际打印顺序序号（printIndex）
这样的映射关系了。

  */
public class 打印任务排序 {
    
    public static class Task {
        int priority; // 任务优先级
        int index; // 初始排队的索引位置
 
        public Task(int priority, int index) {
            this.priority = priority;
            this.index = index;
        }
    }
 
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
 
        Integer[] priorities = Arrays.stream(sc.nextLine().split(",")).map(Integer::parseInt).toArray(Integer[]::new);
 
        int n = priorities.length;
 
        LinkedList<Task> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            queue.addLast(new Task(priorities[i], i));
        }
 
        // 记录结果, results[i] 表示初始排队顺序索引 i 的任务, 实际打印顺序索引为 results[i]
        String[] results = new String[n]; // 定义为String数组, 目的是方便后续打印
 
        // priorities降序
        Arrays.sort(priorities, (a, b) -> b - a);
        // printIndex 既是 priorities中最高优先级的索引位置, 也是实际打印顺序的序号
        int printIndex = 0;
 
        while (!queue.isEmpty()) {
            // 队头任务
            Task task = queue.removeFirst();
 
            if (task.priority == priorities[printIndex]) {
                // 如果队头任务的优先级 是 最高优先级
                // 初始排队序号task.index的任务, 实际打印序号为 printIndex
                results[task.index] = (printIndex++) + "";
            } else {
                // 如果队头任务优先级 不是 最高优先级, 则插入队尾
                queue.addLast(task);
            }
        }
 
        System.out.println(String.join(",", results));
    }

}
